package top.minuy.structure.graph.bipartition.dfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;

/**
 * 检测二分图，深度优先遍历
 *
 * @author Minuy
 * @time 20:21
 * @date 2021/11/19
 */
public class BipartitionDetection {
    public static final boolean BLUE = true;  // 蓝色
    public static final boolean GREEN = false;  // 绿色

    private Graph g;
    private boolean[] isVisited;
    private boolean[] colors;
    private boolean isBipartition = true;

    public BipartitionDetection(Graph g) {
        this.g = g;

        if (g.isDirected()) {
            throw new IllegalArgumentException("BipartiteMatching only works in undirected graph.");
        }

        this.isVisited = new boolean[g.V()];

        this.colors = new boolean[g.V()];

        // 遍历所有联通分量
        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                // 默认给蓝色
                if (!dfs(v, BLUE)) { // 不是二分图
                    isBipartition = false;
                    break;
                }
            }
        }
    }

    /**
     * 判断点是否是蓝色的
     *
     * @param v 要被判断的顶点
     * @return boolean
     * @author Minuy
     * @date 2021/11/29 21:18
     */
    public boolean isBlue(int v) {
        g.validateVertex(v);
        return colors[v] == BLUE;
    }

    private boolean dfs(int v, boolean color) {
        isVisited[v] = true;

        colors[v] = color;

        for (Integer w : g.adj(v)) {
            if (!isVisited[w]) { // 如果没访问过
                // 染色
                if (colors[v] == GREEN) {
                    // colors[w] = BLUE;
                    dfs(w, BLUE);
                } else if (colors[v] == BLUE) {
                    // colors[w] = GREEN;
                    dfs(w, GREEN);
                }

                // 可读性教差，或者说耦合性教高，应该是通过传值的方式完成
//                if (colors[v] == GREEN) {
//                    colors[w] = BLUE;
//                } else if (colors[v] == BLUE) {
//                    colors[w] = GREEN;
//                }

                // 不是只在这里面检测，不管有没有访问过，都应该检测是否合法
//                if (colors[v] == colors[w]) { // 冲突
//                    return false;
//                }
            } else if (isVisited[w]) { // 如果访问过了，检测冲突
                if (colors[v] == colors[w]) { // 冲突
                    return false;
                }
            }
            // 有冗余的检测，没被访问过的是在本节点去赋值的，
            // 所以一定不是冲突的，这里应该是只检测访问过的
//            if (colors[v] == colors[w]) { // 冲突
//                return false;
//            }
        }
        return true;
    }

    /**
     * 给出本图是否是二分图
     *
     * @return boolean 是否是二分图
     * @author Minuy
     * @date 2021/11/19 20:51
     */
    public boolean isBipartition() {
        return isBipartition;
    }

    /**
     * 获取一个分部
     *
     * @param color 要获取分部的颜色
     * @return Iterable<Integer> 分部数组
     * @author Minuy
     * @date 2021/11/19 20:56
     */
    public Iterable<Integer> getPart(boolean color) {
        if (isBipartition()) {
            ArrayList<Integer> res = new ArrayList<>();
            for (int v = 0; v < colors.length; v++) {
                if (colors[v] == color) {
                    res.add(v);
                }
            }
            return res;
        } else {
            throw new IllegalArgumentException("Graph is not a BipartitionGraph.");
        }
    }

    /**
     * 获取蓝色分部
     *
     * @return Iterable<Integer> 蓝色分部数组
     * @author Minuy
     * @date 2021/11/19 20:56
     */
    public Iterable<Integer> blue() {
        return getPart(BLUE);
    }

    /**
     * 获取绿色分部
     *
     * @return Iterable<Integer> 绿色分部数组
     * @author Minuy
     * @date 2021/11/19 20:56
     */
    public Iterable<Integer> green() {
        return getPart(GREEN);
    }
}
